package 力扣.排序;

import java.util.Arrays;

public class BubbleSort {
    public static void main(String[] args) {
//        int[] ints = new int[]{9,8,7,-6,-6,4,4,3,-2,0};
        int[] ints = new int[]{3,2,2,2,2,2,2,2,2};
        bubbleSort3(ints);
        System.out.printf(Arrays.toString(ints));
    }

    private static void bubbleSort1(int[] ints) {
        int n = ints.length;
        for (int i = 0; i < n - 1; i++) {
            boolean flag = true;
            for (int j = n - 1; j > i ; j--) {
                if (ints[j] < ints[j - 1]) {
                    swap(j , j - 1  , ints);
                    flag = false;
                }
            }
            if (flag) {
                return;
            }
        }
    }

    private static void bubbleSort2(int[] ints) {
        int len = ints.length;
        for (int i = 1 ; i < len; i++){
            for (int j = len - 1; j >= i ; j--) {
                if (ints[j] < ints[j - 1]) {
                    swap(j,j - 1,ints);
                }
            }
        }
    }
    private static void bubbleSort3(int[] ints) {
        int len = ints.length;
        for (int i = len - 1 ; i > 0; i--){
            int flag = 1; //with sentinel
            for (int j = 0; j < i ; j++) {
                if (ints[j] > ints[j + 1]) {
                    swap(j,j + 1,ints);
                    flag = 2;
                }
            }
            if (flag == 1) return;
        }
    }

    private static void swap(int i, int j, int[] ints) {
        int p = ints[i];
        ints[i] = ints[j];
        ints[j] = p;
    }

}
